package leetcode.leetcode203;

/**
 * @author czt
 * @version 1.0
 * @since 2024/12/16
 *
 * 根据链表值删除元素
 */
public class Leetcode203 {

    /**
     * 使用哨兵节点来删除
     * @param head 原始链表头节点
     * @param val 节点值
     * @return 原始链表的头节点
     */
    public ListNode removeElements1(ListNode head, int val) {
        // 哨兵节点
        ListNode sentinel = new ListNode(-1, head);

        // 待删除节点的上一个节点
        ListNode p1 = sentinel;
        // 待删除节点
        ListNode p2 = sentinel.next;

        while (p2 != null) {
            if (p2.val == val) {
                // 删除操作， p1指向p2的next，p2向后平移
                p1.next = p2.next;
                p2 = p2.next;
            } else {
                // p1 p2 向后平移
                p1 = p1.next;
                p2 = p2.next;
            }
        }

        return sentinel.next;
    }

    /**
     * 递归
     * @param head 原始链表头节点
     * @param val 节点值
     * @return 原始链表的头节点
     */
    public ListNode removeElements2(ListNode head, int val) {
        if (head == null) {
            return null;
        }

        if (head.val == val) {
            return removeElements2(head.next, val);
        } else {
            head.next = removeElements2(head.next, val);
            return head;
        }
    }

    public static void main(String[] args) {

    }
}
